import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/19 15:22
 * @description 广度优先遍历，对于任何一个查询，构图后，从起点出发，通过广度优先搜索的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();

    }
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int idx = 0;
        // 变量转编号
        Map<String, Integer> map = new HashMap<>();
        for (List<String> e: equations) {
            if (!map.containsKey(e.get(0))) {
                map.put(e.get(0), idx++);
            }
            if (!map.containsKey(e.get(1))) {
                map.put(e.get(1), idx++);
            }
        }
        // 对于每个点，存储其直接连接到的所有点及其对应的权值
        List<Pair>[] edges = new List[idx];
        for (int i = 0; i < idx; i++) {
            edges[i] = new ArrayList<>();
        }
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            int va = map.get(equations.get(i).get(0)), vb = map.get(equations.get(i).get(1));
            edges[va].add(new Pair(vb, values[i]));
            edges[vb].add(new Pair(va, 1.0 / values[i]));
        }
        int queriesCount = queries.size();
        double[] ret = new double[queriesCount];
        // 对于每一次查询，使用广度优先遍历
        for (int i = 0; i < queriesCount; i++) {
            List<String > query = queries.get(i);
            double result = -1.0;
            if (map.containsKey(query.get(0)) && map.containsKey(query.get(1))) {
                // 只有两个变量都出现在map中
                int ia = map.get(query.get(0)), ib = map.get(query.get(1));
                if (ia == ib) {
                    result = 1.0;
                }else {
                    Queue<Integer> points = new LinkedList<>();
                    points.offer(ia);
                    double[] rations = new double[idx];
                    Arrays.fill(rations, -1.0);
                    rations[ia] = 1.0;

                    while (!points.isEmpty() && rations[ib] < 0) {
                        int x = points.poll();
                        for (Pair pair : edges[x]) {
                            int y = pair.index;
                            double val = pair.value;
                            if (rations[y] < 0) {
                                rations[y] = rations[x] * val;
                                points.offer(y);
                            }
                        }
                    }
                    result = rations[ib];
                }
            }
            ret[i] = result;
        }
        return ret;
    }
}

/**
 * 每个点下标和权值
 */
class Pair{
    int index;
    double value;
    public Pair(int index, double value) {
        this.index = index;
        this.value = value;
    }
}
